package tencent;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;

public class Demo2 {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);
        root.left.left.left = new TreeNode(6);
        List<Integer> list = rightSideView(root);
        System.out.println(list);
    }

    public static List<Integer> rightSideView(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        ArrayDeque<TreeNode> arrayDeque = new ArrayDeque<>();
        arrayDeque.offer(root);
        while (!arrayDeque.isEmpty()) {
            //按照每一层的进行遍历
            int size = arrayDeque.size();
            for (int i = 0; i < size; i++) {
                TreeNode poll = arrayDeque.poll();
                if (poll.left != null) {
                    arrayDeque.offer(poll.left);
                }
                if (poll.right != null) {
                    arrayDeque.offer(poll.right);
                }
                if (i == size - 1) {
                    res.add(poll.val);
                }
            }
        }
        return res;
    }
}
